class Solution {
private:
    vector<vector<int>> ans, graph;
    void bfs(int n){
        queue<vector<int>> q;
        vector<int> init;
        init.push_back(0);
        q.push(init);
        while(!q.empty()){
            vector<int> temp = q.front();
            //for(int i = 0; i < temp.size(); i++)cout << temp[i] << " ";
            //cout << endl;
            q.pop();
            int node = temp[temp.size() - 1];
            if(node == n - 1){
                ans.push_back(temp);
                continue;
            }
            for(int i = 0; i < graph[node].size(); i++){
                vector<int> ttemp = temp;
                ttemp.push_back(graph[node][i]);
                q.push(ttemp);
            }
        }
    }   
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        this->graph = graph;
        bfs(graph.size());
        return this->ans;
    }
};